#include<helper.h>
#include<math.h>
int candy(vector<int> &ratings) {
        int i,c,k,n=ratings.size();
        int btm[5000]={0}; //bottom id
        int cnd[5000]={0};//candy
        int nbtm=0;
        //find bottoms
        if (ratings[0]<=ratings[1]) btm[nbtm++]=0;
        for (i=1;i<n-1;i++)
            if (ratings[i]<=ratings[i-1] && ratings[i]<=ratings[i+1]) 
                btm[nbtm++]=i;
         if (ratings[n-1]<=ratings[n-2]) btm[nbtm++]=n-1;

         //calc candies
        for (k=btm[0],c=1;k>=0;k--) cnd[k]=c++;
        for (k=btm[nbtm-1],c=1;k<n;k++) cnd[k]=c++;
        for (i=0;i<nbtm-1;i++){
            for (k=btm[i],c=1;k<btm[i+1] && ratings[k]<=ratings[k+1];k++) cnd[k]=c++;
            for (k=btm[i+1],c=1;k>btm[i] && ratings[k]<=ratings[k-1];k--) cnd[k]=c++;
            if (ratings[k]>ratings[k-1] && ratings[k]>ratings[k+1]) //handle peak
                cnd[k]=max(cnd[k-1],cnd[k+1])+1;
            
        }

        //calc sum of candies
        int res=0;
        for (i=0;i<n;i++) res+=cnd[i];
        //prtIntArr(cnd,10);
        return res;

}

int main(){
    int aa[]={1,5,8,7,1,2,8,8,5,4};
    vector<int> a(aa,aa+1);
    prt(a);
    printf("%d",candy(a));
    int x=36;
    for (int i=2;i--;x--);
    int w3x=pow(2,4);
    return 0;
    
}